#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    void _getMiniR(TreeNode* root, int& min)
    {
        if (root == nullptr)
            return;
        int tmp;
        if (root->left)
        {
            TreeNode* left = root->left;
            while (left)
            {
                tmp = abs(left->val - root->val);
                if (tmp < min)
                    min = tmp;
                left = left->right;
            }
        }
        if (root->right)
        {
            TreeNode* right = root->right;
            while (right)
            {
                tmp = abs(right->val - root->val);
                if (tmp < min)
                    min = tmp;
                right = right->left;
            }
        }
        _getMiniR(root->left, min);
        _getMiniR(root->right, min);
    }
    int getMinimumDifference(TreeNode* root) {
        int min = 100000;
        _getMiniR(root, min);
        return min;
    }
};

lass Solution{
public:
    void _findModeR(TreeNode * root,unordered_map<int,int>&um)
    {
        if (root == nullptr)
            return;
        um[root->val]++;
        _findModeR(root->left,um);
        _findModeR(root->right,um);
    }
    vector<int> findMode(TreeNode * root) {
        vector<int> ret;
        int num;
        unordered_map<int,int> um;
        _findModeR(root,um);
        int maxnum = 0;
        for (auto& e : um)
        {
            if (e.second > maxnum)
                maxnum = e.second;
        }
        for (auto& e : um)
        {
            if (e.second == maxnum)
                ret.push_back(e.first);
        }
        return ret;
    }
};

class Solution {
public:
    int maxnum = 0;
    int num = 0;
    int tmp = 0;
    void GetVector(TreeNode* root, vector<int>& v)
    {
        if (root == nullptr)
            return;
        GetVector(root->left, v);
        v.push_back(root->val);
        if (tmp == root->val)
            num++;
        else
        {
            tmp = root->val;
            num = 1;
        }
        if (maxnum < num)
            maxnum = num;
        GetVector(root->right, v);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> v;
        vector<int> ret;
        GetVector(root, v);
        int left = 0;
        int right = left + maxnum - 1;
        while (right < v.size())
        {
            if (v[left++] != v[right++])
            {
                ret.push_back(v[left]);
                left = right + 1;
                right = left + maxnum - 1;
            }
            else
            {
                left++;
                right++;
            }
        }
        return ret;
    }
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
            return nullptr;
        if (root == p || root == q)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right)
            return root;
        if (!left && right)
            return right;
        else if (left && !right)
            return left;
        else
            return nullptr;
    }
};